// 24. Swap Nodes in Pairs

// Given a linked list, swap every two adjacent nodes and return its head.

// For example,
//    Given 1->2->3->4, you should return the list as 2->1->4->3.
//    Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func swapPairs(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}

	l, swap, step := head.Next, head, head.Next.Next
	swap.Next, swap.Next.Next = step, swap

	for step != nil && step.Next != nil {
		swap.Next, swap = step.Next, step
		step = step.Next.Next
		swap.Next, swap.Next.Next = step, swap
	}

	return l
}

func (l *ListNode) printNode() {
	i := 1
	for l != nil {
		println("i=", i, "v=", l.Val)
		l = l.Next
		i++
	}
}

func main() {
	h, i := new(ListNode), 1
	head := h
	for i < 9 {
		h.Val = i
		h.Next = new(ListNode)
		h = h.Next
		i++
	}
	h.Val = i

	head.printNode()
	head = swapPairs(head)
	println("==========")
	head.printNode()
}
